'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-09 10:21:46
'''
'''
面试题 17.13. 恢复空格
哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

 

示例：

输入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
'''

'''
tips:简单dp，状态dp[i+1]表示sentence[:i+1]的未识别的字符数。假设词典中最长单词长度为l，取l = min(l, len(sentense)),有状态转移方程
dp[i+1] = min(dp[i+1], dp[i+1]) if sentense[i-j:i+1] in dictionary else min(dp[i+1], dp[i-j]+j+1)

式中的j是对l的遍历。

时间复杂度是O(len(sentense)*l),空间复杂度是O(len(sentense))，总体表现还可以。
'''

class Solution:
    def respace(self, dictionary, sentence) -> int:
        import sys
        dictionary = set(dictionary)
        l = max([len(l) for l in dictionary])
        l = min(l, len(sentence))
        dp = [sys.maxsize]*(len(sentence)+1)
        dp[0] = 0
        for i, v in enumerate(sentence):
            for j in range(l+1):
                if sentence[i-j: i+1] in dictionary:
                    dp[i+1] = min(dp[i-j], dp[i+1])
                else:
                    dp[i+1] = min(dp[i+1], dp[i-j]+j+1)
        return dp[-1]


if __name__ == "__main__":
    solution = Solution()
    dictionary = ["looked","just","like","her","brother"]
    sentence = "jesslookedjustliketimherbrother"
    print(solution.respace(dictionary, sentence))